Aiming at the problems of high complexity and long reconstruction time of Generalized Orthogonal Matching Pursuit(GOMP)algorithm,a Stochastic support selection based GOMP(StoGOMP)algorithm was proposed. Firstly,the strategy of stochastic support selection was introduced,and a probability value was randomly generated in each iteration. Then the generated probability value was compared to the preset probability value to determine the selection method of candidate support set. If this probability value was less than the preset probability value,the matching calculation method was adopted,otherwise,the random selection method was adopted. Finally,the residual was updated according to the obtained candidate supports. In this way,the balance between the complexity of the single iteration and the number of iterations of the algorithm was fully considered,and the computational cost of the algorithm was reduced. The experiment of one-dimensional random signal reconstruction shows that the number of samples required for StoGOMP algorithm to achieve 100% reconstruction success rate is reduced by 9. 5% compared with that for GOMP algorithm when the preset probability is 0. 5 and the sparsity is 20. The actual image reconstruction experiment shows that the proposed algorithm has the same reconstruction accuracy as GOMP algorithm,and the reconstruction time of the proposed algorithm is reduced by more than 27% compared to that of the original algorithm when the sampling rate is 0. 5,which indicates that StoGOMP algorithm can effectively reduce the signal reconstruction time.

Aiming at the problem of large number of iterations and long reconstruction time of iterative hard thresholding algorithms in Compressed Sensing (CS), a Hybrid Gradient based Hard Thresholding Pursuit (HGHTP) algorithm was proposed. Firstly, the gradient and conjugate gradient at the current iteration node were calculated in each iteration, and the support sets in the gradient domain and conjugate gradient domain were mixed and the union of these two was taken as the candidate support set for the next iteration, so that the useful information of the conjugate gradient was fully utilized in the support set selection strategy, and the support set selection strategy was optimized. Secondly, the least square method was used to perform secondary screening on the candidate support sets to quickly and accurately locate the correct support and update the sparse coefficients. The experimental results of one-dimensional random signal reconstruction show that HGHTP algorithm needs fewer iterations than the similar iterative hard thresholding algorithms on the premise of guaranteeing the success rate of reconstruction. The two-dimensional image reconstruction experimental results show that the reconstruction accuracy and anti-noise performance of HGHTP algorithm are better than those of similar iterative thresholding algorithms, and under the condition of ensuring reconstruction accuracy, HGHTP algorithm has the reconstruction time reduced by more than 32% compared with similar algorithms.